package com.zp.self.module.level_4_算法练习.算法.位图;

/**
 * @author By ZengPeng
 */
public class 力扣_383_赎金信 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_383_赎金信().canConstruct("a","b"));
        System.out.println(new 力扣_383_赎金信().canConstruct("aa","ab"));
        System.out.println(new 力扣_383_赎金信().canConstruct("aa","aab"));
    }

    /**
     * 题目：给你两个字符串：ransomNote 和 magazine ，
     * 判断 ransomNote 能不能由 magazine 里面的字符构成。
     * 如果可以，返回 true ；否则返回 false 。
     * magazine 中的每个字符只能在 ransomNote 中使用一次。
     *
     * 示例 1：
     * 输入：ransomNote = "a", magazine = "b"
     * 输出：false
     *
     * 分析：
     *      1.使用list存储magazine中的字符遍历，ransomNote中的字符 并在list中移除遍历字符
     *      优雅的解法：StringBuilder  用SB的index 和deleteCharAt 方便一些？  list 与 SB 谁消耗的内存更多呢？？需要看二者源码。
     *      大神解法：位图
     *
     * 边界值 & 注意点：
     *      1.
     **/
    public boolean canConstruct(String ransomNote, String magazine) {
        //方案3：大神解法--位图
        int[]  arr = new int[26];
        for (char c : magazine.toCharArray())
            arr[c - 97]+=1;
        for (char c : ransomNote.toCharArray()) {
            arr[c - 97]-=1;
            if(arr[c - 97]<0)return false;
        }
        return  true;

        //方案2：StringBuilder
//        StringBuilder sb = new StringBuilder(magazine);
//        int index;
//        for (int i = 0; i < ransomNote.length(); i++) {
//            index = sb.indexOf(String.valueOf(ransomNote.charAt(i)));
//            if(index!=-1)
//                sb.deleteCharAt(index);
//            else return  false;
//        }
//        return  true;

        //方案1：list
//        ArrayList<Character> characterList=new ArrayList<>();
//        for (int i = 0; i < magazine.length(); i++)
//            characterList.add(magazine.charAt(i));
//        for (int i = 0; i < ransomNote.length(); i++) {
//            Character c = ransomNote.charAt(i);
//            if(!characterList.remove(c))return false;
//        }
//        return  true;
    }
}
